<?php


namespace XiaoGuai\DataStructure\String;


class SampleString
{

    /**
     *             !
     * i 0 1 2 3 4 5 6 7 8
     *   a b c d e f g h j
     *      [c d e g x x]
     * j     0 1 2 3 x x
     *             ^
     * i回溯到i-j+1, j重新从0开始
     */

    /**
     * 在字符串中搜索子串,返回子串的位置
     * 思想: 将模式串与字符串对齐,依次对比每一位,若不匹配,i回溯到之前的下一位再继续匹配
     * @param string $string
     * @param string $search
     * @param int $offset
     * @return int
     */
    public static function posBF(string $string, string $search, int $offset = 0): int
    {
        // 获取字符串数组
        $chars = str_split($string);
        $searches = str_split($search);
        $chars_length = strlen($string);
        $search_length = strlen($search);
        $i = $offset;
        $j = 0;

        // 同时循环比较i和j
        while ($i < $chars_length && $j < $search_length) {
            // 比较两个字符
            if ($chars[$i] == $searches[$j]) {
                // 两个字符匹配
                $i++;
                $j++;
            } else {
                // 两个字符不匹配,回溯
                $i = $i - $j + 1; // 先回退i
                $j = 0; // j回退到0
            }
        }

        if ($j == $search_length) {
            // 字符串search已经完全匹配通过
            return $i - $search_length;
        }

        return -1; // 没有匹配到
    }

    /**
     * 在字符串中搜索子串,返回子串的位置
     * 思想: 将模式串与字符串对齐匹配,当不匹配时,i不回溯,j回溯到next_j位置
     * @param string $string
     * @param string $search
     * @param int $offset
     * @return int
     */
    public static function posKMP(string $string, string $search, int $offset = 0): int
    {
        // 获取字符串数组
        $chars = str_split($string);
        $searches = str_split($search);
        $chars_length = strlen($string);
        $search_length = strlen($search);
        $i = $offset;
        $j = 0;
        $next = self::getNext($search);

        // 同时循环比较i和j
        while ($i < $chars_length && $j < $search_length) {
            // 比较两个字符
            if ($chars[$i] == $searches[$j]) {
                // 两个字符匹配,若相等，则都前进一步
                $i++;
                $j++;
            } else {
                // 两个字符不匹配,i不回溯,只回溯j
                $j = $next[$j]; // j回退到0
            }
        }

        if ($j == $search_length) {
            // 字符串search已经完全匹配通过
            return $i - $search_length;
        }

        return -1; // 没有匹配到
    }


    /**
     *
     * string     a    b    c    d    a    b    d    p    ^
     * index      0    1    2    3    4    5    6    7    8
     * next_j    -1    0    0    0    0    1    2    0    0   最长[真后缀]长度
     * next_val
     *
     * next_j表示当匹配到第j位置不匹配时,需要回溯的位置
     * @link https://segmentfault.com/a/1190000008575379
     * @link https://www.zhihu.com/question/21923021
     * @link https://www.cnblogs.com/yjiyjige/p/3263858.html
     *
     * 解释: 真后缀表示主字符串i前的n位,真后缀=1,
     *      真前缀表示模式字符串的前n位,真前缀=1,
     *      真后缀=1,真前缀=1, 表示主串的前1位=模式串的前1位,则可以减少比对1次, j可以移到1位置,否则j不能移到1位置
     *      真后缀=2,真前缀=2, 表示主串的前2位=模式串的前2位,则可以减少比对2次, j可以移到2位置,否则j不能移到2位置
     *      真后缀=3,真前缀=3, 表示主串的前3位=模式串的前3位,则可以减少比对3次, j可以移到3位置,否则j不能移到3位置
     *      真后缀=4,真前缀=4, 表示主串的前4位=模式串的前4位,则可以减少比对4次, j可以移到4位置,否则j不能移到4位置
     *      真后缀=5,真前缀=5, 表示主串的前5位=模式串的前5位,则可以减少比对5次, j可以移到5位置,否则j不能移到5位置
     * 当j=6时,后缀有1-5长度,若最长真后缀=2,表示1,3,4,5都不可以,所以1,3,4,5位置不用比较了,直接移到2继续比较即可
     *
     *                                    i
     * string    [a   b   c   d   a   b] {m}  g   k   h   p   x
     *            ---------------------
     * match      a   b   c   d   a   b  {d}  p   ^
     *                                    j
     *
     * 此时i的"m"与j处的"d"不匹配,按BP算法需要进行回溯,回溯后,i从原初始位置前进一位,j整体右移一位
     *                i
     * string    [a   b   c   d   a   b] {m}  g   k   h   p   x
     *                -----------------
     * match          a   b   c   d   a   b  {d}  p   ^
     *                j
     * 此时需要对比主字符串string的[b,c,d,a,b]与模式串的[a,b,c,d,a]
     * 也就是对比模式串原来j=6位置前面的6位子串[a,b,c,d,a,b]的模式串的真前缀[a,b,c,d,a]与真后缀[b,c,d,a,b]
     * 若提前预知j=7的前6位子串的5位真前缀与5位真后缀不匹配,则模式串整体右移一位不匹配,不能只移一位
     *
     *
     *                                    i
     * string    [a   b   c   d   a   b] {m}  g   k   h   p   x
     *            ---------------------
     * match      a   b   c   d   a   b  {d}  p   ^
     *
     *
     * 此时i的"m"与j处的"d"不匹配,按BP算法需要进行回溯,因上面分析回溯到原来后面一位不行,则需回溯至两位,
     * 回溯后,i从原初始位置前进2位,j整体右移2位
     *                    i
     * string    [a   b   c   d   a   b] {m}  g   k   h   p   x
     *                    -------------
     * match              a   b   c   d  {a}  b   d   p   ^
     *                    j
     * 此时需要对比主字符串string的[c,d,a,b]与模式串的[a,b,c,d]
     * 也就是对比模式串原来j=6前面的5位子串[a,b,c,d,a]的模式串的真前缀[a,b,c,d]与真后缀[b,c,d,a]
     * 若提前预知j=6的紧邻前5位子串的4位真前缀与4位真后缀不匹配,则模式串整体右移2位不匹配,不能只移2位
     * [回溯n位对比的实质是对比已匹配的模式串的前几位字符子串的长度的真前缀(模式串)与真后缀(主串)]
     * [若真前后缀匹配的长度越长,则回溯的长度就越长,优先从回溯最远的地方继续比较]
     */


    /**
     *
     * string      a    b    c    d    a    b    d    p    ^
     * index[i]    0    1    2    3    4    5    6    7    8
     * next[j]    -1    0    0    0    0    1    2    0    0   最长[真后缀匹配]长度
     *
     * next[0]=-1,j已经在最左边了，不可能再移动了，这时候要应该是i指针后移
     * next[1]=0,显然，j指针一定是后移到0位置的。因为它前面也就只有这一个位置了
     */

    /**
     * KMP中寻找next数组(当search的第n位不匹配时需要回溯的位置数组)
     * 原理: 当模式串不匹配时,已经匹配了前面n-1个,此时字符串中此n-1个与模式串相同,只需要提前计算出当到第n
     *      个不匹配时,j需要回溯到的位置即可
     * 前j-1位真前后缀匹配的最长长度(长度越长,回溯的距离越远)
     *
     * 原理: 已知next[j], 当P[k]=P[j]时,有next[j+1]=next[j] + 1
     * @param string $search
     * @return array
     */
    protected static function getNext(string $search): array
    {
        $next = [];
        $search_length = strlen($search);
        $chars = str_split($search);
        $j = 0; // $chars的下标
        $k = -1;
        $next[0] = -1; // 表示当第0位不匹配时,j不动,i需要后移一位

        while ($j < $search_length - 1) {
            if ($k == -1 || $chars[$j] == $chars[$k]) {
                // 如果相等,next[j+1]=next[j] + 1
                $next[$j + 1] = $next[$j] + 1;
                $k++;
                $j++;
            } else {
                // 字符串不相同
                $k = $next[$k];
            }
        }
        return $next;
    }

    protected static function getNextVar(string $search): array
    {
        $next = [];
        $search_length = strlen($search);
        $chars = str_split($search);
        $j = 0; // $chars的下标
        $k = -1;
        $next[0] = -1; // 表示当第0位不匹配时,j不动,i需要后移一位

        while ($j < $search_length - 1) {
            if ($k == -1 || $chars[$j] == $chars[$k]) {
                if ($chars[$j + 1] == $chars[$k + 1]) {
                    // 当两个字符相等时要跳过
                    $next[$j + 1] = $next[$k + 1];
                } else {
                    $next[$j + 1] = $k + 1;
                }
                $k++;
                $j++;
            } else {
                // 字符串不相同
                $k = $next[$k];
            }
        }
        return $next;
    }
}